package 每日一题;

import java.util.HashMap;
import java.util.Map;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-19
 **/

public class No211添加与搜索单词 {

    static class WordDictionary {

        private TrieNode root = new TrieNode('-');

        public WordDictionary() {

        }

        public void addWord(String word) {
            TrieNode cur = this.root;
            char[] arr = word.toCharArray();
            for (char c : arr) {
                TrieNode nextOrDefault = cur.next.getOrDefault(c, new TrieNode(c));
                cur.next.put(c, nextOrDefault);
                cur = nextOrDefault;
            }
            cur.setWorld(true);
        }

        public boolean search(String word) {
            TrieNode cur = this.root;
            char[] arr = word.toCharArray();
            return this.search(arr, 0, cur);
        }

        private boolean search(char[] arr, int index, TrieNode cur) {

            if (cur == null) {
                return false;
            }

            if (index == arr.length) {
                return cur.isWorld;
            }

            char c = arr[index];
            if (c == '.') {
                for (Map.Entry<Character, TrieNode> entry : cur.next.entrySet()) {
                    if (this.search(arr, index + 1, entry.getValue())) {
                        return true;
                    }
                }
                return false;
            } else {
                return this.search(arr, index + 1, cur.next.get(c));
            }

        }

    }

    static class TrieNode {

        private Character c;
        private Map<Character, TrieNode> next;
        private boolean isWorld;

        public TrieNode(Character c) {
            this.c = c;
            this.next = new HashMap<>();
        }

        public void setWorld(boolean world) {
            this.isWorld = world;
        }
    }

    public static void main(String[] args) {
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("at");
        wordDictionary.addWord("and");
        wordDictionary.addWord("an");
        wordDictionary.addWord("add");
        wordDictionary.search("a");
        wordDictionary.search(".at");
        wordDictionary.addWord("bat");
        wordDictionary.search(".at");
        wordDictionary.search("an.");
        wordDictionary.search("a.d.");
        wordDictionary.search("b.");
        wordDictionary.search("a.d");
        System.out.println(wordDictionary.search("."));
    }

}
